Technical Field
The present disclosure relates to global registration and structure-from-motion and, more particularly, to systems and methods to perform absolute rotation estimation including outlier detection via low-rank and sparse matrix decomposition.
Description of the Related Art
The problem of absolute rotation estimation arises in both global registration of three-dimensional (3D) point sets and in structure-from-motion techniques. Absolute rotation estimation attempts to recover absolute rotations for a set of local reference frames with respect to a global reference frame, given estimates of the relative rotations between attitudes of such local reference frames. For example, the local reference frames can be local coordinates where three-dimensional (3D) points are represented, as typically posed by a 3D point set registration problem, or may be camera reference frames, as typically posed in the context of structure-from-motion.
Global registration (also known as N-view point set registration) consists in finding a rigid transformation that brings multiple 3D point sets into alignment. Global registration can be solved in point space (e.g. through the use of correspondences) or in frame space. Global registration solutions that operate in the point space typically attempt to simultaneously optimize all rotations with respect to a cost function that depends on the distance between corresponding points. On the other hand, global registration solutions that operate in the frame space typically attempt to optimize criteria that are related to the internal coherence of a network of rotations (and translations) applied to the local coordinate frames.
The structure-from-motion problem (also known as block orientation in the context of photogrammetry) consists in recovering both a scene structure, such as 3D scene points, and camera motion, such as absolute positions and attitudes of the cameras. Structure-from-motion methods can be divided into three categories: structure-first, structure-and-motion, and motion-first. Structure-first approaches (e.g. independent models block adjustment) first build stereo-models and then co-register them, similarly to the 3D registration problem. Structure-and-motion techniques (e.g. bundle block adjustment, resection-intersection methods, hierarchical methods, etc.) are the most common and solve simultaneously for both “structure” and “motion.”
Finally, motion-first methods first recover the “motion” and then compute the “structure.” These motion-first methods are global, as they take into account simultaneously the entire epipolar graph, whose vertices represent the cameras and edges link images having consistent matching points. Most of such approaches solve the structure-from-motion optimization problem in two steps. In the first step, the absolute rotation of each image is computed, and in the second step camera translations are recovered.
Several approaches for performing absolute rotation estimation have been proposed. For example, one proposal distributes the error along all cycles in a cycle basis, while another casts the problem as an optimization of an objective function where rotations are parameterized as quaternions. Another proposed solution uses a gradient descent method based on matrix completion.
However, one main drawback of the global techniques noted above is that they suffer dramatically in the presence of outlying relative rotation estimates. For example, in the structure-from-motion context, repetitive structures or textures in the images cause mismatches which skew the epipolar geometry. In the global registration context, outliers are caused by faulty pairwise registration, which in turn may be caused by insufficient overlap and/or poor initialization.
Thus the above discussed techniques often require a preliminary step to detect and remove outliers prior to computation of the absolute rotations. For example, approaches for identification of outlier epipolar geometries can check for cycle consistency (i.e. deviation from identity) within the epipolar graph.
Importantly, such preliminary outlier detection strategies are known to be computationally demanding and require speed to be balanced against accuracy. For example, approaches based on random sample consensus (RANSAC) suffer from the limitation of increased computational complexity for large-scale datasets. In particular, recent research has shown that outlier removal is the most expensive step within the structure-from-motion pipeline after feature extraction and matching.
Therefore, systems and methods to perform absolute rotation estimation including outlier detection are desired. In particular, computationally-inexpensive techniques to perform absolute rotation estimation including outlier detection are desired.